import com.sun.source.tree.Tree;

import java.util.Stack;


public class Main {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           if(root == null ){
               return root;
           }
           if(root == p || root== q){
               return root;
           }
           TreeNode left = lowestCommonAncestor(root.left, p, q);
           TreeNode right = lowestCommonAncestor(root.right, p, q);
           if(left != null && right != null){
               return root;
           }else if (left != null){
                   return  left;
               }else {
               return right;
           }
    }
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
         if(root == null){
             return  false;
         }
        stack.push(root);
         if(root == node){
             return true;
         }
        boolean flgLeft = getPath(root.left, node, stack);
         if (flgLeft){
             return true;
         }
        boolean flgRight = getPath(root.right, node, stack);
        if (flgRight){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,
                                          TreeNode p, TreeNode q) {
       if (root == null){
           return null;
       }
       Stack<TreeNode> stack1 = new Stack<>();
       Stack<TreeNode> stack2 = new Stack<>();
       getPath(root,p,stack1);
       getPath(root,p,stack2);
       int size1 = stack1.size();
       int size2 = stack2.size();
       if(size1 > size2){
           int size = size1 - size2;
           while (size != 0){
               stack1.pop();
               size--;
           }
       }else {
           int size = size2 -size1;
           while (size != 0){
               stack2.pop();
               size--;
           }
       }
       while (!stack1.isEmpty() && !stack2.isEmpty()){
           if (stack1.peek().equals(stack2.peek())){
               return  stack1.pop();
           }
           stack1.pop();
           stack2.pop();
       }
      return null;
    }

    //从前序与中序遍历序列构造二叉树
    public  int preIndex;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
             return buildTreeChild(preorder,inorder,0,inorder.length-1);
        }
private TreeNode  buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
    if (inBegin > inEnd) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[preIndex]);
    int rootIndex = findRootIndex(inorder, inBegin, inEnd, preorder[preIndex]);
    preIndex++;
    root.left = buildTreeChild(preorder, inorder, inBegin, rootIndex - 1);
    root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inEnd);
    return root;
}
private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key){
           for (int i = inBegin;i <= inEnd;i++){
               if (inorder[i] == key){
                   return i;
               }
           }
           return -1;
}


    //从中序与后序遍历序列构造二叉树

    public int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(inorder,postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTreeChild(int[] inorder, int[] postorder, int inBegin, int inEnd) {
        if (inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findRootIndex(inorder, inBegin, inEnd, postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder, postorder, rootIndex+ 1,inEnd);
        root.left = buildTreeChild(inorder, postorder, inBegin, rootIndex-1);
        return root;
    }

    private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}






